package com.yang.Backtracking;

// 深度优先搜索
// 电话号码的字母组合
import java.util.ArrayList;
import java.util.List;
import java.util.List;

//import java.util.List;
//
//// 考虑边界问题 对应数字能代表的字符串  0以及* # 是否需要考虑在内？  空字符串如何处理
public class LeetCode17 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "101023";
        solution.restoreIpAddresses(s);
    }
}
//class Solution {
//    public List<String> letterCombinations(String digits) {
//
//    }
//}


class Solution {
    List<String> result;
    public List<String> restoreIpAddresses(String s) {
        result = new ArrayList<>();
        if(s.length() < 4 || s.length() > 12) return result;
        backtracking(s, 0, 0);
        return result;
    }
    private void backtracking(String s, int startIndex, int split){
        if(split == 3){
            if(isValid(s, startIndex, s.length() - 1)){
                result.add(s);
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s, startIndex, i)){
                s = s.substring(0, i + 1) + '.' + s.substring(i + 1);
                // 插入点后索引应当+1
                backtracking(s, i + 2, split + 1);
                // 回溯删除插入的点
                s = s.substring(0, i + 1) + s.substring(i + 2);
            }else{
                // 不合法那后面都不会合法了
                break;
            }
        }
    }

    private boolean isValid(String s, int left, int right){
        // if(left > right){
        //     return false;
        // }
        // 开头是0的不合法串
        if(s.charAt(left) == '0' && left != right){
            return false;
        }
        int sum = 0;
        for(int i = left; i <= right; i++){
            // 不合法字符串
            if(s.charAt(i) < '0' || s.charAt(i) > '9'){
                return false;
            }
            sum = sum*10 + (s.charAt(i) - '0');
            // 超出数值范围
            if(sum > 255){
                return false;
            }
        }
        return true;
    }
}

